codefandomcom-20200214-history
Matrix multiplication
Introduction Prerequisites It is assumed that those reading this have a basic understanding of what a matrix is and how to add them, and multiply them by scalars, i.e. plain old numbers like 3, or -5. A secondary school algebra course would probably give one more than enough background, but is surely not required by any means. If you need some background Go here Matrix Multiplication Basics In order to multiply 2 matrices given one must have the same amount of rows that the other has columns. In other words two matrices can be multiplied only if one is of dimension m×n and the other is of dimension n×p where m, n, and p are natural numbers {m,n,p \in \mathbb{N} }. The resulting matrix will be of dimension m×p. Example 4x2 Multiplied by 2x4 Take a matrix 4x2 call it \mathbf{A} ; another of dimension 2x4 and call it \mathbf{B} . Give them some arbitrary values and lets do some multiplication. \mathbf{A} = \begin{bmatrix} 2 & 3 & -1 & 0 \\ -7 & 2 & 1 & 10 \end{bmatrix} \mathbf{B} = \begin{bmatrix} 3 & 4 \\ 2 & 1 \\ -1 & 2 \\ 2 & 7 \end{bmatrix} Our result matrix is going to be 2×2 as you will see as we go step by step. First we multiply and sum the first row with the first column: 2(3) + 3(2) + (-1)(-1) + 0(2). Then we do the same for the first row and second column: 2(4) + 3(1) + (-1)(2)+ 0(7), etc. To make a long story short, our matrix would be: \mathbf{AB} = \begin{bmatrix} 2(3) + 3(2) + (-1)(-1) + 0(2) & 2(4) + 3(1) + (-1)(2) + 0(7) \\ -7(3) + 2(2) + 1 (-1) + 10(2) & -7(4) + 2(1) + 1 (2) + 10(7) \end{bmatrix} = \begin{bmatrix} 13 & 9 \\ 2 & 46 \end{bmatrix} As this implies, multiplication is non-commutative in general for matrices, i.e. \mathbf{AB} \ne \mathbf{BA} since in this case if we reversed the order the resulting matrix \mathbf{BA} would be 4×4 instead of 2×2. More General Approach Now lets visualize A and B as m×n and n×p matrices respectively. \mathbf{A} = \begin{bmatrix} a_{1,1} & a_{1,2} & \dots & \dots \\ a_{2,1} & a_{2,2} & \dots & \dots \\ a_{3,1} & a_{3,2} & \ddots & \dots \\ \vdots & \vdots & \vdots & a_{m,n} \end{bmatrix} \mathbf{B} = \begin{bmatrix} b_{1,1} & b_{1,2} & \dots & \dots \\ b_{2,1} & b_{2,2} & \dots & \dots \\ b_{3,1} & b_{3,2} & \ddots & \dots \\ \vdots & \vdots & \vdots & b_{n,p} \end{bmatrix} We are going to be adding and multiplying like before, but generally. \mathbf{AB} = \begin{bmatrix} a_{1,1}b_{1,1} + a_{1,2}b_{2,1} + \dots + a_{1,n}b_{p,1} & \dots \\ \vdots & a_{m,1}b_{1,1} + a_{m,2}b_{2,p} + \dots + a_{m,n}b_{n,p} \end{bmatrix} Pseudocode & General Algorithm So now that we have a general idea of what a matrix is, and how to multiply them in general, we can derive some pseudocode around it. We could break down the steps as follows. # Check the sizes of two matrices \mathbf{A} (m×n) and \mathbf{B} (t×u): if n = t then we can multiply them otherwise no (in that order \mathbf{AB} ) # If they can be multiplied, then create a new matrix of size m by u # For each row in A and each column in \mathbf{B} multiply and sum the elements and the place the results in the rows and columns of the result matrix \mathbf{AB} Here is some pseudocode treating matrices like if they have a m element and an n element, so the dimension of a matrix object is m×n. multiplyMatrix(matrix1, matrix2) -- Multiplies rows and columns and sums them multiplyRowAndColumn(row, column) returns number var total: number begin for each rval in row and cval in column begin total += rval*cval end return total end begin -- If the rows don't match up then the function fails if matrix1:n != matrix2:m return failure; dim = matrix1:n -- Could also be matrix2:m newmat = new squarematrix(dim) -- Create a new dim x dim matrix for each r in matrix1:rows and c in matrix2:columns begin end end Implementations C Sharp // Program in C# to multiply two matrices using Rectangular arrays. using System; class MatrixMultiplication { int, a; int, b; int, c; public void ReadMatrix() { Console.WriteLine("\n Size of Matrix 1:"); Console.Write("\n Enter the number of rows in Matrix 1 :"); int m=int.Parse(Console.ReadLine()); Console.Write("\n Enter the number of columns in Matrix 1 :"); int n=int.Parse(Console.ReadLine()); a=new intm,n; Console.WriteLine("\n Enter the elements of Matrix 1:"); for(int i=0;i VB.NET Public Module MatrixMultiplication ' Generic stand-alone method ' Uses LINQ. Public Function Multiply(matrix1 As IEnumerable(Of IEnumerable(Of Double)), _ matrix2 As IEnumerable(Of IEnumerable(Of Double)) As IEnumerable(Of IEnumerable(Of Double)) If matrix1.Count = matrix2(0).Count Then Dim ret(matrix1(0).Count, matrix2.Count) As Double For i As Integer = 0 To ret.Count - 1 For j As Integer = 0 To ret(0).Count - 1 ret(i, j) = 0 For k As Integer = 0 To matrix1(0).Count - 1 ret(i, j) = ret(i, j) + a(i, k) + b(k, j) Next Next Next Else Throw New RankException("Number of columns in matrix1 is not equal to the number of rows in matrix2.") End If End Function ' This method can be run in a console app. Public Sub Main() Dim m_1 As Integer, n_1 As Integer, m_2 As Integer, n_2 As Integer Try Console.WriteLine("Size of matrix 1:") Console.Write("Number of rows: ") m_1 = Integer.Parse(Console.ReadLine()) Console.Write("Number of columns: ") n_1 = Integer.Parse(Console.ReadLine()) Dim matrix1(m_1, n_1) As Double Console.WriteLine("Enter the elements of matrix 1:") For i As Integer = 0 To m_1 - 1 For j As Integer = 0 To n_1 - 1 Console.Write("Element at " & i & ", " & j) matrix1(i, j) = Integer.Parse(Console.ReadLine()) Next Next Console.WriteLine("Size of matrix 2:") Console.Write("Number of rows: ") m_2 = Integer.Parse(Console.ReadLine()) Console.Write("Number of columns: ") n_2 = Integer.Parse(Console.ReadLine()) Console.WriteLine("Enter the elements of matrix 2:") For i As Integer = 0 To m_2 - 1 For j As Integer = 0 To n_2 - 1 Console.Write("Element at " & i & ", " & j) matrix2(i, j) = Integer.Parse(Console.ReadLine()) Next Next Dim product(,) As Double = Multiply(matrix1, matrix2) Console.WriteLine("The product of the two matrices is:") For i As Integer = 0 To product.Count - 1 For j As Integer = 0 To product(0).Count - 1 Console.Write(product(i, j) & " ") Next Console.WriteLine() Next Catch ex As Exception Console.WriteLine("An error occured. The message associated with the error was:") Console.WriteLine(ex.Message) End Try Console.WriteLine() Console.WriteLine("Press any key to exit.") Console.ReadKey() End Sub End Module Python def multmat(a,b): m=len(a) n=len(a0) k=len(b) res=[] if len(b) != 1: p=len(b0)-1 else: p=0 if len(b) 0: print('bad size') elif n!=k: print('bad size') else: #print('good size') n=k #print('k=',k,'n=',n) for q in range(m): res.append(0) #print('res=',res) for q in range(m): for w in range(p): resq.append(0) for i in range(m): for j in range(p+1): for r in range(n): #print('ijr:res',i,j,r,res) resij =air*brj+resij return res Ruby class MatrixMultiplication { int, a; int, b; int, c; public void ReadMatrix() { Console.WriteLine("\n Size of Matrix 1:"); Console.Write("\n Enter the number of rows in Matrix 1 :"); int m=int.Parse(Console.ReadLine()); Console.Write("\n Enter the number of columns in Matrix 1 :"); int n=int.Parse(Console.ReadLine()); a=new intm,n; Console.WriteLine("\n Enter the elements of Matrix 1:"); for(int i=0;i